package 图;
import java.util.Deque;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.ArrayDeque;
import java.util.Arrays;

/**
 * tomorrow  实现 dijktra 算法  以及 堆优化 算法 (堆 的   改 写 ) 
 * 以及 堆 的 写法  
 * 以及  这几道 图的  相应题目 
 * 对图   进行  一个 复习
 */
/**
 * 如果 涉及 到一些 弊端的 话 那就 
 * 在 使用 最暴力的 建图 方式 
 * 也是 最通用的 建图 方式 (左程云的 那种 建图方式)
 * 
 * 如果 涉及 到 入度 
 * 出度
 *  之类的  操作 要怎么 办
 *  
 * 这种 建图的 方式 肯定 也有 其 解决 方法 
 * 
 * 要不然 也不会 有这么 多的 人 利用 这个 建图的 方式 
 * 
 * 可能 这里 还有一些 优化的 小技巧 
 * 把所有  属性 （包括  声明的 数组） 都 设置 为    static
 * 
 *  因为 这样 的话 只会加载 一次  直接 声明 一个 最大  范围 的 数组 
 * 可能  这  对 leetcoe 上面  的 样例 可以 
 * 因为 leetcode 的 操作 你也看过 源码  也明白 是 怎么 回事 
  *  
  *  这里 就不这样 操作 了 
 * @author I adore you
 *
 */
public class 链式前向星 {
       int N ; //节点的 个数
    	int M ;// 边 的个 数  
	//  上面的  两个 变量 只是 为了 初始化 下面的 数组 
	
	//  把 数组 的 值 一开始 全部 初始化 为  - 1 这是 为了 后面的   判断  边界
	int head [];
	
	/**
	 * head[]  尽量 开的 比 节点的 个数        大一  点  至少 要比节点 个数 多一
	 * 一定 要初始化 为  Arrays.fill(head,-1)   - 1  无论  bfs  还是dfs  这一点 很重要 结束的 标志  
	 */
	
	Edge [] edges ;
	int idx = 0;
	/**
	 * 采用的  是  头插法
	 */
	void add(int from,int to ,int weight ) {
		edges[idx].to = to;
		edges[idx].weight = weight;
		edges[idx].next = head[from];
		head[from] = idx++;
	}
	/**
	 * 假设 是  无向图 
	 * martix 中的   一维数组 中的 arr[0] = from arr[ 1] = to arr[ 2] = weight
	 */
	void initialGraph(int martix[][],int n) {
		// 这里  不对吧  martix.length 是  边的 个数   节点的 个数  不知道 一般 题上 会给出  吧
//		int  n = martix.length;
		int len = martix.length * martix.length;
		head = new int [n + 1];
		edges = new Edge [len ]; 
		/**
		 * 这里 注意 一下 edges = new Edge [ len]  这个 数组 里面存储的的 可是
		 * 引用数据变量   要赋值 的 不然 会 报 NullPointer 异常的 
		之前 踩过 这个 坑 了这里 要 注意 一下
		 */
		Arrays.fill(head, -1);
		for(int  i = 0 ;i < len  ;i++) {
			edges[i] = new Edge();
		}
		for(int arr [] : martix) {
			//无向图
			add(arr[0],arr[1],arr[2]);
			add(arr[1],arr[0],arr[2]);
		}
	}
	void bfs (int root) {
		Deque<Integer> queue = new ArrayDeque<>();
		//  也可以 用 数组 来  模拟 这个       visited  效率 会更  一些
		HashSet<Integer> visited = new HashSet<>();
		visited.add(root);
//		queue.offer(root);
		queue.addLast(root);
		while(!queue.isEmpty()) {
			int cur = queue.poll();
			System.out.println(cur);
			for(int edgeIndex = head[cur] ; edgeIndex != -1;edgeIndex = edges[edgeIndex].next) {
				int to = edges[edgeIndex].to;
				if(!visited.contains(to)) {
					queue.addLast(to);
					visited.add(to);
				}
			}
		}
	}
	HashSet<Integer> vis = new HashSet<>();
	//  dfs  用  栈 但是用递归的 话 就不需要 自己 显示 调用 stack 的 api 了
	void dfs(int root) {
		vis.add(root);
		System.out.println(root);
		//  这不是 熟悉的 递归里面 套用 for 循环 嘛 对吧
		for(int  edgeIndex = head[root]; edgeIndex != -1 ;edgeIndex = edges[edgeIndex].next) {
			int to = edges[edgeIndex].to;
			if(!vis.contains(to)) {
				vis.add(to);
				dfs(to);
			}
		}
	}
	public static void main(String []args) {
		链式前向星  test  = new 链式前向星 ();
		int [][]martix = {{2,1,1},{2,3,1},{3,4,1}};
//		int martix[][] = {{0,1,3},{0,2,7},{0,3,21},{3,4,1},{3,5,14},{4,5,2},{1,3,2}};
//		int [][] martix = {{0,1,1},{1,2,1},{2,4,1},{3,4,1},{0,3,1},{0,2,1}};
		test.initialGraph(martix, 5);
//		test.bfs(0);
		System.out.println("**************************");
//		test.dfs(0);
//		test.dijkstraOne(0);
//		System.out.println(Arrays.toString(test.dis));
		System.out.println("&&&&&&&****************");
	     test.dijkstraTwo(2);
		System.out.println(Arrays.toString(test.dis));
	}
	
	/**
	 *用链式前向星 的 方式 来 写 dijkstra  这种算法
	 * 
	 * 这个  dis[i][j]   就是  从 root  开始到其他节点 的 最短 距离 
	 * 左程云 那个 是 用  一个 HashMap 来做的  常数 时间复杂度 肯定比较 高的 
	 * dis  二维 数组 开多大 呢  ??
	 * 其实 这个 用  一维 数组 就够了 
	 * 因为  求的 是     单点  最短  距离 
	 */
	static int INF = Integer.MAX_VALUE; 
	int dis [] = new int [11];
//	  下面 两种 方式 都可以吧
	boolean vis1[] = new boolean [11];
	int vis2 [] = new int [101];
//	Arrays.fill(dis,INF);
	void dijkstra(int root) {
		Arrays.fill(dis,INF);
		// 自己 到自己的 距离 为  0
		dis[root] = 0;
		vis1[root] = true;
		for(int edgeIndex = head[root] ;edgeIndex != -1;edgeIndex = edges[edgeIndex].next) {
			int  to = edges[edgeIndex].to;
			int  w  = edges[edgeIndex].weight;
			if(!vis1[to]) {
				dis[to] = w;
				vis1[to] = true;
			}
			else {
//				if(dis[to] > dis)
			}
		}
	}
	void dijkstraOne(int root) {
//		  感觉可以 不用 做
		Arrays.fill(dis, INF);
		dis[root] = 0;
		Deque<Integer> queue = new ArrayDeque<>();
		queue.addLast(root);
		while(!queue.isEmpty()) {
			int cur = queue.pollFirst();
//			  如果 已经 锁死的 点 就 跳过了  因为它的  所有 节点 已经更新过了  果然 放在 这个 位置是错的
//			if(vis1[cur])
//				continue;
			for(int edgeIndex = head[cur] ;edgeIndex != -1;edgeIndex = edges[edgeIndex].next) {
//				 if (vis1[cur]) ??
				int w = edges[edgeIndex].weight;
				int to = edges[edgeIndex].to;
				/**
				 * 上面那个位置的效率 不如   这个 
				 *   这个位置 是 最合 理 的  就是效率 最高的       
				 */
				if(vis1[to])
					continue;
				if(dis[to] > dis[cur] + w) {
					dis[to] = dis[cur] + w;
//					 加入队列
					queue.addLast(to);
				}
			}
			//上面的 代码执行过后  当前 cur 的所有 后续 节点 距离 都更新 那 cur 就 需要 被 锁死 了
			vis1[cur] = true;
			/**
			 * 当前节点  已经 更新 过了    需要 找出  距离  cur  "最近 "的 的 一个邻接点开始 下一次" 距离" 更新 
			 * 所以 下面 采用 最暴力的  方式 来 找   直接 
			 * 遍历 整个 queue 找出最小值 放在  queue 的 最前面 
			 * 但是 这个 过程 要怎么 去完成 呢 (选择 排序的 方式 不就可以 对吧)
				因为 我用 的 这个 数据结构 ArrayDeque  底层 就是 一个数组
				但是 这里的 object  没有 索引  index 这一说 
			下面 提供一种 最暴力的 做法  先找 到 最小 值 然后 delete 掉 
			在 addFirst 这种  最暴力  (后面 再去 想 下 能不能 用其他数据 结构代替吧)
			 */
			// 找到 最小值 
			if(!queue.isEmpty()) {
				int minDis = INF;
				int index = 0;
				for(int  i : queue) {
					if(minDis > dis[i]) {
						minDis = dis[i];
						index = i;
					}
				}
//			 移除 min
				queue.remove(index);
//			  再 把    min  加到 队列的 最前面
				queue.addFirst(index);
			}
		}
	}
	/**
	 * 其他的 部分 都一样 就是  在  挑选出 
	 * 最近    邻接点 的时候 的 方法 不一样  
	 * @param root
	 * 
	 * 他  是 这样   对堆 进行 优化 的 
int martix[][] = {{0,1,3},{0,2,7},{0,3,21},{3,4,1},{3,5,14},{4,5,2},{1,3,2}};
  以 这个 图  进行  举例 说明 
  new Dis (3,21);  new Dis (2,7)  ;  new  Dis(1,3)  这是 在 0 节点之后 priorityQueue 里面的 数据
  然后 弹出  Dis(1,3)   会新产生 一个 最短路径 Dis(3,5) 这个 时候的 处理 就是 直接 加进去 直接 queue.offer();
 这个 时候 Dis(3,5)   是在  优先队列的 头部的  不管 在哪个位置    Dis(3,5) 一定 先 比 Dis (3,21) 先出队列  
 那这个 时候 Dis (3,21) 出来的 时候 编号 3   已经 被加入 到 vis1[3] = true; 
 所以 这  直接 跳过 
 这就是 他这个 实现的 一个 原理  
 
 
 左程云的 那种 dijkstra 的堆优化   是 直接 把 堆 给 改写 了 
 使用 自己 手写的 堆 来 优化 这种 有时间去 研究 一下   他那种的 算法
 在此 之前 首先 要把 堆 相关的  代码 要 给  写熟 对吧
 	 */
	void dijkstraTwo(int root) {
		Arrays.fill(dis, INF);
		Arrays.fill(vis1, false);
		dis[root] = 0;
		PriorityQueue<Dis> queue = new PriorityQueue<>((o1,o2) -> (o1.dis - o2.dis));
		queue.offer(new Dis(root,0));
		while(!queue.isEmpty()) {
			Dis cur = queue.poll();
			/**
			 * 优化 之后 这个 if 条件的 位置其实 放在 这里 和 放在 for 循环当中 都是 一样的 差 不多
			 * 但是不采用 这种方式  的堆优化的话   
			 * 可能 就会有区别 了 这里先注意 一下
			 */
			if(vis1[cur.index])
				continue;
			for(int edgeIndex = head[cur.index] ; edgeIndex != -1 ;edgeIndex = edges[edgeIndex].next) {
				int to = edges[edgeIndex].to;
				int w = edges[edgeIndex].weight;
				if(vis1[to])
					continue;
				if(dis[to]  > w + dis[cur.index]){
					dis[to] = w + dis[cur.index];
					queue.offer(new Dis(to,dis[to]));
				}
			}
			vis1[cur.index] = true;
		}
	}

}
/**
 * 可以 用数组 进行 模拟 也可以 
 * 使用一个 类 来进行  模拟
 *  板子 采用的 是 int [] 数组 进行模拟  
 */
class Dis{
	int index;
	int dis;
	public Dis(int index,int dis) {
		this.index = index;
		this.dis = dis;
	}
	//  时刻 记住 加个 空参数 的 构造器
	public Dis() {
		
	}
}
class Edge{
	int to;
	int weight;
//  直接 初始化 为 -1
	int next = -1;
	
}